#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <functional>


void swapPair(std::pair<int, int>& a, std::pair<int, int>& b) {
    std::pair<int, int> temp = { a.first, a.second };

    a.first = b.first;
    a.second = b.second;

    b.first = temp.first;
    b.second = temp.second;
}

void printVector(std::vector<int>& nums) {
    for (int i{}; i < nums.size(); i++) {
        std::cout << nums[i] << " ";
    }
    std::cout << std::endl;
}

void printPair(std::pair<int, int>& a) {
    std::cout << "first: " << a.first << "  second: " << a.second << "\n";
}

// 方法1：统计频率，排序
// 快速排序
void quickSort(std::vector<std::pair<int, int>>& vec, int l, int r) {
    int low = l, high = r;
    if (low < high) {
        while (low < high) {
            while (vec[low].second <= vec[l].second && low < r) {
                low++;
            }
            while (vec[high].second >= vec[l].second && high > l) {
                high--;
            }
            if (low < high) {
                swapPair(vec[low], vec[high]);
            } else {
                break;
            }
        }
        swapPair(vec[l], vec[high]);
        quickSort(vec, l, high - 1);
        quickSort(vec, high + 1, r);
    }
}

// 计算每个数出现的次数
// 对次数进行排序并记录
std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
    std::map<int, int> frequentMap;
    for (int i{}; i < nums.size(); i++) {
        frequentMap[nums[i]]++;
    }

    std::vector<std::pair<int, int>> tempPair;
    for (auto it = frequentMap.begin(); it != frequentMap.end(); it++) {
        tempPair.push_back({ it->first, it->second });
    }

    quickSort(tempPair, 0, tempPair.size() - 1);

    std::vector<int> res;
    std::cout << "temp pair vec size: " << tempPair.size() << "\n";
    int tempSize = tempPair.size();
    for (int i = tempSize - 1; i >= tempSize - k; i--) {
        res.push_back(tempPair[i].first);
    }

    return res;
}
// end


// 方法2：优先队列（小顶堆）

// 定义比较函数 通过class重载()操作符，定义一个对象
class cmp {
public:
    bool operator()(std::pair<int, int>& a, std::pair<int, int>& b) {
        return a.second > b.second;
    }
};

std::vector<int> topKFrequent2(std::vector<int>& nums, int k) {
    std::map<int, int> frequentMap;
    for (int i = 0; i < nums.size(); i++) {
        frequentMap[nums[i]]++;
    }

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, cmp> pq_max;
    for (auto it = frequentMap.begin(); it != frequentMap.end(); it++) {
        if (pq_max.size() >= k) {
            if (pq_max.top().second < it->second) {
                pq_max.pop();
                pq_max.push({ it->first, it->second });
            }
        } else {
            pq_max.push({ it->first, it->second });
        }
    }

    std::vector<int> res;
    while (!pq_max.empty()) {
        std::pair<int, int> item = pq_max.top();
        printPair(item);
        res.push_back(item.first);
        pq_max.pop();
    }

    return res;
}


int main() {
    // // test for swapPair function
    // std::pair<int, int> a = { 10, 5 };
    // std::pair<int, int> b = { 2, 1 };

    // std::cout << "before===\n";
    // printPair(a);
    // printPair(b);
    // swapPair(a, b);
    // std::cout << "after===\n";
    // printPair(a);
    // printPair(b);
    // // end



    // // test for quickSort
    // std::vector<std::pair<int, int>> p;
    // p.push_back({ 1, 1 });
    // p.push_back({ 2, 10 });
    // p.push_back({ 3, 4 });
    // p.push_back({ 4, 4 });
    // p.push_back({ 5, 2 });
    // p.push_back({ 6, 3 });
    // std::cout << "before===\n";
    // for (int i = 0; i < p.size(); i++) {
    //     printPair(p[i]);
    // }
    // quickSort(p, 0, p.size() - 1);
    // std::cout << "after===\n";
    // for (int i = 0; i < p.size(); i++) {
    //     printPair(p[i]);
    // }
    // // end



    std::vector<int> nums = { 1, 5, 5, 7, 1, 1 };
    std::vector<int> res = topKFrequent2(nums, 2);
    printVector(res);
}